package main

import "fmt"

// 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
// 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

func removeElement(nums []int, val int) int {
	// 优化: 假设只有第一个元素是val,其他位置的元素其实并不需要前移
	// [val,1,2,3,4,5]
	// [5,1,2,3,4,_]

	// 实现: 把 后面的!val 移动到 前面的val位置, 然后i不动,继续判断
	i, j := 0, len(nums)-1
	for i <= j {
		// 前面找到val位置
		if nums[i] != val {
			// 只有!val时,i才前进
			i++
			continue
		}
		// 把后面的值直接移动过来,继续判断 (原因是:假设后面移动过来的是val,则相当于废了一个元素,此时接着继续废即可)
		nums[i] = nums[j]
		j--
	}
	return i
}

func removeElementV4(nums []int, val int) int {
	// 把 !val 都移动到最前面

	// 优化: 假设只有第一个元素是val,其他位置的元素其实并不需要前移
	i, j := 0, 0
	cnt := 0
	for j < len(nums) {
		if nums[j] != val {
			// 把!val存起来
			nums[i] = nums[j]
			cnt++
			i++
		}
		j++
	}
	return cnt
}

func removeElementV3(nums []int, val int) int {
	i := 0
	j := len(nums) - 1

	cnt := 0
	for i <= j {
		if i == j {
			if nums[i] != val {
				cnt++
			}
			break
		}

		// 找到 val
		for nums[i] != val && i < j {
			// 里面都是 !val
			i++
			cnt++
		}

		// 找到 !val
		for nums[j] == val && i < j {
			// 里面都是 val
			j--

			// [j]=val
		}
		// [j] = !val

		// 前面的改成!val,  继续向后找
		if i < j {
			nums[i] = nums[j]
			cnt++ // [i]=val
		}
		if i == j {
			if nums[i] != val {
				cnt++
			}
			break
		}

		// 继续向后找
		i++
		j--
	}

	return cnt
}

func removeElementV2(nums []int, val int) int {
	cnt := 0
	index := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != val {
			cnt++
			nums[index] = nums[i]
			index++
		}
	}
	return cnt
}

func main() {
	nums := []int{3, 2, 2, 3}
	fmt.Println(nums, removeElement(nums, 3))
}
